
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1698. -- [Usaco2007 Feb]Lilypad Pond 荷叶池塘 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1698: [Usaco2007 Feb]Lilypad Pond 荷叶池塘</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>101&nbsp;&nbsp;<span class=green>Solved: </span>29<br>[<a href='submitpage.php?id=1698'>Submit</a>][<a href='problemstatus.php?id=1698'>Status</a>][<a href='bbs.php?id=1698'>Discuss</a>]</center><h2>Description</h2><div class=content>
为了便于牛们欣赏和锻炼，农夫JOHN在他的农场上新添加了一个美丽的池塘。

JOHN的池塘是一个长方形，他已经把它划分成了M行N列的小正方行 (1 <= M 
<= 30; 1 <= N <= 30). 某些正方行里是石头，另外一些则是特别结实的荷叶，其余
则只有清水。

为了锻炼，Bessie想从一片荷叶跳到另外一片。她的每一次跳跃都是一个象棋中的
马步：两行一列或一行两列。

JOHN看到了Bessie并且发现有时Bessie没有办法达到她的目标荷叶。他准备添加
一些荷叶来让Bessie完成她的目标。当然，荷叶不能放在石头上。

帮助JOHN找出他最少要放多少片荷叶和他一共有多少种放最少片荷叶的方案。
</div><h2>Input</h2><div class=content>第1行： 两个整数， M 和 N。
第2~M+1行： 第i+1包含N个数，分别为第i行的N个格子的情况。 0表示格子
为空，1表示有一片荷叶，2表示格子里有石头，3表示此格子是Bessie的起点，4
表示此格子是Bessie的目标。
</div><h2>Output</h2><div class=content>
第1行： 一个数，最少情况下需要添加的荷叶数目。如果没有方案存在，输出-
1。
第2行： 一个数，达到最小值的方案总数。这个数保证不超过内设64位整数(long 
long/ int64)的大小。如果第一行是-1，不要输出此行。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 5<br />
1 0 0 0 0<br />
3 0 0 0 0<br />
0 0 2 0 0<br />
0 0 0 4 0<br />
<br />
输入解释：<br />
池塘含4行5列。Bessie在第2行第1列并且想跳到第4行第4列。池塘里有1块<br />
石头和3片荷叶。<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2<br />
3<br />
<br />
输出解释：<br />
<br />
至少需要2片荷叶。一共有三种摆法：<br />
	第4行第2列，第2行第3列<br />
	第1行第3列，第3行第2列<br />
	第1行第3列，第2行第5列<br />
<br />
          R1C2,R2C3     R1C3,R3C2     R1C3,R2C5<br />
          1 0 0 0 0     1 0 X 0 0     1 0 X 0 0<br />
          3 0 X 0 0     3 0 0 0 0     3 0 0 0 X<br />
          0 0 2 0 0     0 X 2 0 0     0 0 2 0 0<br />
          0 X 0 4 0     0 0 0 4 0     0 0 0 4 0<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1698'>Submit</a>][<a href='problemstatus.php?id=1698'>Status</a>][<a href='bbs.php?id=1698'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
